A key component in a communication system is the medium used to transport information. Any failure at this level results in corrupted information or loss of information. Particular media are more prone to generating such failures than others. For instance, a radio wave link is more likely to introduce problems in the communication than an optical fibre link. Fibre links are well shielded from outside light, so no or little noise can be inserted into the information transported over the link. A radio wave link however, will easily interfere with other radio waves in the air. Thus, a radio link is to be considered a lossy medium, a fibre link is not. Another example of a lossy medium is a copper telephone wire which is used to transport xDSL (Digital Subscriber Line) signals between an access multiplexer e.g. a DSLAM and the customer premises equipment, e.g. an ADSL or VDSL modem of the end-user.
One way to resolve the problem of corrupted information or information loss relies on adding error detection codes or error correction codes to the information. Examples are Cyclic Redundancy Check (CRC) and Parity bits. Either of these can be added to a piece of information, and the receiver is able to generate the CRC or parity bit based on the information which was received. By comparing the received CRC or parity information with the generated CRC or parity information, the receiver is able to detect and eventually correct corrupted information.
A document published by Xilinx on Mar. 23, 2001 entitled “IEEE 802.3 Cyclic Redundancy Check” describes the working of CRC32 and its use at the data link layer.
Error correction does not only detect corrupted information. It is also able to correct (limited) corruption. Where the transmitter for instance encodes the information with a convolution code, for like the Trellis diagram, and the receiver decodes the information using for instance the Viterbi algorithm, a number or errors resulting from transmission over a lossy medium, may be corrected at the receiver's end.
When information is lost or the information is corrupted beyond repair, retransmission is a common method to recover the information. A receiver can track which information has been received in comparison to the information that was expected. At particular times the receiver may request the missing information to be retransmitted. In other words, the transmitter assumes correct delivery of each packet unless explicitly informed about a failure. Another retransmission scenario wherein the transmitter keeps track of all the information that was sent but is not yet acknowledged by the receiver requires more intelligence from the transmitter. Such intelligence involves recording the time between transmitting a packet and receiving an acknowledgement, and in case this time is too long or no acknowledgement is received, automatically retransmitting the packet.
An example of protocols used for retransmission are Automatic Repeat reQuest (ARQ) protocols. There are several variants of the ARQ protocol, for instance Stop and Wait ARQ or Sliding Window ARQ. An explanation on these forms of ARQ can be found in IETF RFC 3366, published in August 2002, in particular section 1.4 thereof. RFC 3366 can be retrieved from the Internet via the URL: http://www.ietf.org/rfc/rfc3366.txt.
Digital information is typically sent over the medium in pieces called packets which are of limited size. The packet size can be fixed, e.g. Asynchronous Transfer Mode (ATM) cells, or variable, e.g. Internet Protocol (IP) packets. When a part of these packets consists of a CRC block, the effective bandwidth decreases and relatively more packets are required to transmit a particular set of information. For example: if 1024 bits of information are to be transmitted and packets are 128 bits large, 8 packets are required to transmit all the information. In case each packet contains 16 bits of CRC code, only 112 bits of information fit in a single packet and 10 packets are required to transmit all the information.
In cases where retransmission is used to recover from corrupted packets or lost packets, overhead is introduced as well. A single packet is transmitted and retransmitted, taking up the time and bandwidth of a different packet. Referring to the previous example, if 8 packets are to be sent, but a packet is lost and requires retransmission, a total of 9 packets are transmitted over the link.
Retransmission and error detection or error correction are not the only reasons for overhead on a communication link. Several protocols provide end-to-end reliability. An example of such a protocol is the Transmission Control Protocol (TCP) which provides what appears to be a dedicated link between two endpoints. The TCP protocol describes how this link is established between source and destination and how transmission of information on this link becomes reliable irrespective of the physical medium that is used. The link appears to be dedicated as it can go over a multitude of nodes and types of links, which can be reliable or lossy.
IETF RFC 793 published in September 1981 describes the TCP protocol and illustrates how TCP can be used for reliable communication. In particular section 2.6 describes the working of TCP retransmission. RFC 793 can be retrieved from the Internet via the URL: http://www.ietf.org/rfc/rfc793.txt.
TCP numbers each segment in the stream of data that flows between source and destination. The destination can use these sequence numbers to determine which parts are still missing. The destination notifies the source of missing packets and the source can send those particular packets again. A problem with this TCP scheme is that notification of a missing packet and the retransmission are end-to-end. End-to-end retransmission creates overhead on all the links between the nodes on the route between the end systems. In case of multicast traffic, end-to-end retransmission becomes really problematic. If hundreds of systems miss a part of a stream, the single source would be flooded with retransmission requests. If only one destination is missing a packet, a retransmission request to the source may lead to excess bandwidth occupancy on all links in the multicast tree because the packet will be re-multicasted.
Applications such as triple-play, which involve the combination of regular data, voice data and video data transfer on a single link, demand higher reliability from the networks between content provider and end user. Regular data transmission is generally not time or resource critical. Retrieving emails or a website can cope with short delays in the information stream. Voice data is more critical. Although the loss of a single voice packet goes unnoticed to the human ear, loss of various packets leads to serious audible noise. The influence of lost video packets is visible to the human eye. Therefore, traffic has to be prioritized in a triple-play setup so each type of traffic is delivered timely with the necessary reliability to reduce negative effects. As lossy media are a common part of access networks and increase the probability of incorrect packets significantly, they pose a severe difficulty in deploying a triple-play network.
Another problem which arises in networks is Head Of The Line blocking (HoL). This phenomenon appears when multiple links or data flows are aggregated onto a single flow. This typically appears in situations where First In First Out (FIFO) buffers are used in some way to improve network functionality. These buffers can be used to receive information packets from incoming links before they are forwarded on an outgoing link. For instance, a device having three incoming links and one outgoing link may contain three input buffers and one output buffer. These input buffers are used as a queue for received packets before they are transmitted onto the outgoing link. Head of the Line blocking arises when information packets destined for a particular outgoing link cannot reach that link due to congestion on another link. For instance, if there are two outgoing links and three incoming links with buffers, HoL may arise when one of the outgoing links is congested and all incoming link buffers have a packet for that link at the head of the buffers. Packets with a destination on the other outgoing link can no longer reach that link because their buffer is blocked by a packet for the congested link. Another example is when a particular high priority information packet is blocked due to retransmission of a low priority packet, for instance when both packets travel end-to-end and arrive on the same incoming link of a switching or routing device
It is an objective of the present invention to create a more reliable link over a lossy medium. It is another objective of the present invention to offer a more effective retransmission scheme, i.e. a retransmission scheme which introduces less overhead and which is able to respect traffic priority. It is also an objective of the present invention to provide a retransmission scheme which does not require any modifications to end systems. It is another objective of the present invention to selectively protect particular traffic and ignore other traffic for protection. It is another objective of the present invention to reduce head of the line blocking.